package algotithm.leetcode.dichotomy.test349;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @author zhouyanxiang
 * @Date 2021-01-2021/1/8-10:09
 */
public class Solution {

    public static void main(String[] args) {
        int[] nums1 = {1,2,2,1};
        int[] nums2 = {2,22,2};
        Solution solution = new Solution();
        int[] intersection = solution.intersection(nums1, nums2);
        for (int i = 0; i < intersection.length; i++) {
            System.out.print(intersection[i] + " ");
        }
    }

    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums2.length; i++) {
            if (binarySearch(nums1,nums2[i]) && !set.contains(nums2[i])) {
                set.add(nums2[i]);
            }
        }
        int[] arr = new int[set.size()];
        int index = 0;
        for (int num : set) {
            arr[index++] = num;
        }
        return arr;
    }

    public boolean binarySearch(int[] arr,int target) {
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            int mid = i + j >> 1;
            if (arr[mid] > target) {
                j = mid - 1;
            } else if (arr[mid] < target) {
                i  = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
}
